//给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。 
//
// 示例 1: 
//
// 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
//输出: true
// 
//
// 示例 2: 
//
// 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
//输出: false 
// Related Topics 字符串 动态规划 
// 👍 283 👎 0

package leetcode.editor.cn;

//leetcode submit region begin(Prohibit modification and deletion)
class P97InterleavingString {
	public boolean isInterleave(String s1, String s2, String s3) {
		int n1 = s1.length();
		int n2 = s2.length();
		int n3 = s3.length();
		if (n1 + n2 != n3) {
			return false;
		}
		if (n1 == 0) {
			return s2.equals(s3);
		}
		if (n2 == 0) {
			return s1.equals(s3);
		}

		boolean[][] dp = new boolean[n1 + 1][n2 + 1];
		dp[0][0] = true;
		for (int i = 1; i < n1 + 1; i++) {
			dp[i][0] = dp[i - 1][0] && (s1.charAt(i - 1) == s3.charAt(i - 1));
		}
		for (int i = 1; i < n2 + 1; i++) {
			dp[0][i] = dp[0][i - 1] && (s2.charAt(i - 1) == s3.charAt(i - 1));
		}

		for (int i = 1; i <= n1; i++) {
			for (int j = 1; j <= n2; j++) {
				dp[i][j] =
						(dp[i - 1][j] && (s1.charAt(i - 1) == s3.charAt(i + j - 1))) || (dp[i][j - 1] && (s2.charAt(j - 1) == s3.charAt(i + j - 1)));
			}
		}
		return dp[n1][n2];

	}
}
//leetcode submit region end(Prohibit modification and deletion)
